using System;
using System.Collections.Generic;

namespace LeetCode {
    public class MaxArea {
        public int MaxRectangleArea (int[] height) {
            int area = 0;
            Stack<int> stack = new Stack<int> ();
            for (int i = 0; i < height.Length; i++) {
                if (stack.Count == 0 || (height[i] >= height[stack.Peek ()])) {
                    stack.Push (i);
                    continue;
                }
                while (stack.Count != 0 && (height[i] < height[stack.Peek ()])) {
                    int idx = stack.Pop ();
                    if (stack.Count == 0) {
                        area = Math.Max (height[idx] * i, area);
                    } else {
                        area = Math.Max (area, height[idx] * (i - stack.Peek () - 1));
                    }
                }
                stack.Push (i);
            }
            while (stack.Count != 0) {
                int idx = stack.Pop ();
                if (stack.Count == 0) {
                    area = Math.Max (height[idx] * height.Length, area);
                } else {
                    area = Math.Max (area, height[idx] * (height.Length - stack.Peek () - 1));
                }
            }
            return area;
        }
    }
}